package gps;

import gps.util.BoardGenerator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

public class FillZoneBoard implements Cloneable {
	private Square[][] board;
	
	public FillZoneBoard(int dimension) {
		this.board = BoardGenerator.getRandomMatrix();
	}
	
	public FillZoneBoard(Square[][] board) {
		this.board = board;
	}

	public int getDimension(){
		return board.length;
	}
	
	public Square getTopLeft() {
		return board[0][0];
	}

	public void clearVisits() {
		for (int i = 0 ; i < board.length ; i++) {
			for (int j = 0 ; j < board.length ; j++) {
				board[i][j].setVisited(false);
			}
		}
	}
	
	public boolean validSquare(int i, int j) {
		return !(i < 0 || i >= board.length || j < 0 || j >= board.length);
	}
	
	/**
	 * Propagates through the board the colour
	 */
	
	public void propagateColour(Colour targetColour){
		Colour sourceColour = getTopLeft().getColour();
		doPropagateColour(sourceColour, targetColour, 0, 0);
		clearVisits();
		return;
	}
	
	private void doPropagateColour(Colour sourceColour, Colour targetColour, int i, int j) {
		// current square has different colour than top-left corner original one, stop propagation
		if (board[i][j].isVisited() || !board[i][j].getColour().equals(sourceColour)) {
			return;
		} else {
			board[i][j].setColour(targetColour);
			board[i][j].setVisited(true);
			
			if (validSquare(i-1,j)){
				doPropagateColour(sourceColour,targetColour, i-1, j);	// North neighbour
			}
			if (validSquare(i,j+1)){
				doPropagateColour(sourceColour,targetColour, i, j+1);	// West neighbour
			}
			if (validSquare(i+1,j)){
				doPropagateColour(sourceColour,targetColour, i+1, j);	// South neighbour
			}
			if (validSquare(i,j-1)){
				doPropagateColour(sourceColour,targetColour, i, j-1);	// East neighbour
			}
		}
	}
	
	public int getColourCount(){
		Set<Colour> colours = new HashSet<Colour>(); 
		for (int i = 0; i < board.length ; i++) {
			for (int j = 0; j < board.length ; j++) {
				colours.add(board[i][j].getColour());
				if (colours.size()==Colour.values().length){
					return colours.size();
				}
			}
		}
		return colours.size();		
	}
	
	public boolean hasOneColour(){
		Colour mainColour = getTopLeft().getColour();
		for (int i = 0; i < board.length ; i++) {
			for (int j = 0; j < board.length ; j++) {
				if (!board[i][j].getColour().equals(mainColour)){
					return false;
				}
			}
		}
		return true;
		
	}
	
	class SquareWithDistance{
		public Square square;
		public int distance;
		
		public SquareWithDistance(Square square, int distance) {
			this.square = square;
			this.distance = distance;
		}
	}
	
	public int getFarClusterDistance() {
		Queue<SquareWithDistance> queue = new PriorityQueue<SquareWithDistance>(board.length*board.length,new Comparator<SquareWithDistance>() {
			@Override
			public int compare(SquareWithDistance o1, SquareWithDistance o2) {
				return o1.distance-o2.distance;
			}
		});
		int[][] distances = new int[board.length][board.length]; 
		for (int i = 0; i < board.length ; i++) {
			for (int j = 0; j < board.length ; j++) {
				distances[i][j] = Integer.MAX_VALUE;
			}
		}
		int maxDistance = 0;
		
		distances[0][0]=0;
		queue.add(new SquareWithDistance(board[0][0], distances[0][0]));
		
		while (!queue.isEmpty()){
			SquareWithDistance current = queue.poll();
			int i = current.square.getX();
			int j = current.square.getY();
			
			//south neighbour
			if (validSquare(i+1, j)){
				int edgeValue = board[i][j].getColour().equals(board[i+1][j].getColour())?0:1;
				if (distances[i+1][j]>distances[i][j]+edgeValue){
					distances[i+1][j] = distances[i][j]+edgeValue;
					if (distances[i+1][j]>maxDistance){
						maxDistance = distances[i+1][j];
					}
					queue.add(new SquareWithDistance(board[i+1][j], distances[i+1][j]));
				}
			}
			//north neighbour
			if (validSquare(i-1, j)){
				int edgeValue = board[i][j].getColour().equals(board[i-1][j].getColour())?0:1;
				if (distances[i-1][j]>distances[i][j]+edgeValue){
					distances[i-1][j] = distances[i][j]+edgeValue;
					if (distances[i-1][j]>maxDistance){
						maxDistance = distances[i-1][j];
					}
					queue.add(new SquareWithDistance(board[i-1][j], distances[i-1][j]));
				}
			}
			//east neighbour
			if (validSquare(i, j+1)){
				int edgeValue = board[i][j].getColour().equals(board[i][j+1].getColour())?0:1;
				if (distances[i][j+1]>distances[i][j]+edgeValue){
					distances[i][j+1] = distances[i][j]+edgeValue;
					if (distances[i][j+1]>maxDistance){
						maxDistance = distances[i][j+1];
					}
					queue.add(new SquareWithDistance(board[i][j+1], distances[i][j+1]));
				}
			}
			//west neighbour
			if (validSquare(i, j-1)){
				int edgeValue = board[i][j].getColour().equals(board[i][j-1].getColour())?0:1;
				if (distances[i][j-1]>distances[i][j]+edgeValue){
					distances[i][j-1] = distances[i][j]+edgeValue;
					if (distances[i][j-1]>maxDistance){
						maxDistance = distances[i][j-1];
					}
					queue.add(new SquareWithDistance(board[i][j-1], distances[i][j-1]));
				}
			}
			
		}
		queue.clear();
		return maxDistance;
	}

	public List<Colour> getNeighboursColours(){
		List<Colour> neighboursColours = new ArrayList<Colour>();
		Colour sourceColour = getTopLeft().getColour();
		doGetNeighboursColours(neighboursColours, sourceColour, 0, 0);
		clearVisits();
		return neighboursColours;
	}
	
	private void doGetNeighboursColours(List<Colour> neighboursColours, Colour sourceColour, int i, int j){
		// Out of the board finish condition...
		if (!validSquare(i, j)) {
			return;
		// current square has different colour than top-left corner original one, stop propagation
		} else if (board[i][j].isVisited() || !board[i][j].getColour().equals(sourceColour)) {
			if (!board[i][j].isVisited() && !neighboursColours.contains(board[i][j].getColour())){
				neighboursColours.add(board[i][j].getColour());
			}
			return;
		} else {
			board[i][j].setVisited(true);
			doGetNeighboursColours(neighboursColours,sourceColour, i-1, j);	// North neighbour
			doGetNeighboursColours(neighboursColours,sourceColour, i, j+1);	// West neighbour
			doGetNeighboursColours(neighboursColours,sourceColour, i+1, j);	// South neighbour
			doGetNeighboursColours(neighboursColours,sourceColour, i, j-1);	// East neighbour
		}		
	}
	
	public int getMainClusterSize(){
		Colour sourceColor = getTopLeft().getColour();
		return doGetMainClusterSize(sourceColor,0,0);
	}
	
	public int doGetMainClusterSize(Colour sourceColour, int i, int j){
		if (!validSquare(i, j)) {
			return 0;
		// current square has different colour than top-left corner original one, stop propagation
		} else if (board[i][j].isVisited() || !board[i][j].getColour().equals(sourceColour)) {
			return 0;
		} else {
			board[i][j].setVisited(true);
			
			int north = doGetMainClusterSize(sourceColour, i-1, j);
			int west = doGetMainClusterSize(sourceColour, i, j+1);
			int south = doGetMainClusterSize(sourceColour, i+1, j);
			int east = doGetMainClusterSize(sourceColour, i+1, j-1);
			return 1 + north + west + south + east;
		}
	}
	

	@Override
	public String toString() {
		String board = "";
		for (int i = 0 ; i < this.board.length ; i++) {
			for (int j = 0 ; j < this.board.length ; j++) {
				board += this.board[i][j].getColour().toString() + " ";
			}
			board += "\n";
		}
		
		return board;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + Arrays.deepHashCode(board);
		return result;
	}
	
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		FillZoneBoard other = (FillZoneBoard) obj;
		if (!Arrays.deepEquals(board, other.board))
			return false;
		return true;
	}
	
	@Override
	public FillZoneBoard clone() {
		Square[][] cloneBoard = new Square[board.length][board.length];
		
		// clones the board manually because this.board.clone doesn't perform a deep copy!!!
		for (int i = 0 ; i < board.length ; i++) {
			for (int j = 0 ; j < board.length ; j++) {
				cloneBoard[i][j] = this.board[i][j].clone();
			}
		}
		return new FillZoneBoard(cloneBoard);
	}
}